1. Field of the Invention
The disclosed invention generally relates to apparatus for Galois Field multiplication, and particularly to bit-serial Galois Field multipliers.
2. Description of Related Art
Data communications and processing systems transmit and receive digital data which are generally signal representations of binary bits. Since, during the transfer of data, errors sometimes occur, various techniques have been developed over the years for increasing the probability of error-free data transfer.
Particular error detecting and/or correcting techniques are directed to algebraic block codes wherein binary numbers are utilized to represent elements in a finite or Galois Field (GF). Specifically, a Galois Field (2.sup.m) has 2.sup.m elements each m bits in length. These field elements may be considered as binary vectors representing data words or "symbols." For example, a Galois Field (2.sup.3) has eight elements, each three bits long. Typically, such Galois Field elements are multiplied in processes used to encode and decode messages for error correcting purposes. Error correcting code techniques, including the algegbra of Galois Fields, are described, for example, in "Error-Correcting Codes," by W. W. Peterson and E. J. Weldon, Jr., published by MIT Press, 1972.
Galois Field multiplication is fundamental in algebraic code techniques and usually involves complicated operations. One known technique for implementating Galois Field multiplication uses logarithmic look-up tables with intermediate shifting and adding steps. Another known technique for Galois Field multiplication involves shifting and adding the individual bits of the operands in a predetermined sequence. This shifting and adding technique is typically implemented with shift registers and/or common logic elements.
Still another method for performing Galois Field multiplication is implemented at the bit level, using "bit-serial" multipliers that accept m-bit symbols serially and produce bit-serial, m-bit output symbols. Such types of Galois Field multipliers are typically preferred in systolic array processors.
Specific examples of known Galois Field multipliers are disclosed in U.S. Pat. No. 4,037,093, issued to Gregg, et al.; U.S. Pat. No. 4,251,875, issued to Marver, et al. and U.S. Pat. No. 4,567,600 to Massey and Omura. Another known Galois Field multiplier is disclosed in "VLSI Design of a Reed-Solomon Encoder Using a Berlekamp Bit Serial Multiplier Algorithm," by I. S. Reed et al. (source unknown).
Known Galois Field multipliers have, however, generally been too complex or too specialized and hence of too limited capability. For example, the multiplication technique disclosed in the above-cited Massey and Omura patent cannot be used with Galois Field primitive root polynomials having linearly dependent roots; although, in practice, the most commonly encountered Galois Fields are those having linearly dependent roots. The multiplication technique of Berlekamp, on the other hand, is understood from the above-cited Reed et al. article to require representing the operands (i.e., symbols) in a dual basis which, in turn, requires translational logic, such as a ROM, between the two bases. A disadvantage of such a multiplication technique is that the size of the translational logic increases with the size of the field, and different logic is required for each different field.
Further, prior art Galois Field multipliers are relatively slow and, as a result, may be unable to operate at the speeds necessary to support required data rates with more powerful codes. Less powerful codes would thus be required to support the required data rates.